package com.wl2o2o.lanqiao.xzfourteen;

import java.util.Arrays;

/** 
* @author : WLei224
* @date ：2023年3月30日 上午10:03:16 
* 
*/
public class 归并排序{
	   public static void main(String[] args){
	      //归并排序采用的也同样是递归思想：现将数组一分为二，左边递归不断一分为二进行归并，右边同理
	      int a[] = {51,46,20,18,95,67,82,30};
	      mergeSort(a,0,a.length-1);
	      System.out.println(Arrays.toString(a));

	   }

	   //写递归归并算法
	   public static void mergeSort(int a[], int left, int right){
	      int mid = (right + left) / 2;
	      if(left<right){
	          mergeSort(a,left,mid);
	          mergeSort(a,mid+1,right);
	          merge(a,left,mid,right);  
	      }
	   }

	   //进行归并
	   public static void merge(int a[], int left, int mid, int right){
	      //用于整合合并
	      int temp[] = new int[right - left + 1];
	      int i = left, j = mid + 1, k = 0;
	      while(i <= mid && j <= right ){
	          if(a[i] < a[j]) temp[k++] = a[i++];
	          else            temp[k++] = a[j++];
	          
	      }
	      while(i <= mid)temp[k++] = a[i++];
	      while(j <= right)temp[k++] = a[j++];
	      
	      
	      for(int x = 0; x < temp.length; x++) a[left+x] = temp[x];
	      
	   }
	}
